/*
 * @lc app=leetcode.cn id=332 lang=cpp
 *
 * [332] 重新安排行程
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ans;
        if (tickets.empty()) {
            return ans;
        }
        unordered_map<string, multiset<string>> hash;
        for (const auto & ticket: tickets) {
            hash[ticket[0]].insert(ticket[1]);
        }
        stack<string> s;
        s.push("JFK");

        // 实际上这个栈操作利用了
        // 测试用例必然满足全部票可以使用的条件

        // 并不是很直观，很难想象出图的遍历过程

        // 从递归角度看更自然一些：

        // 就是给定起点和剩余票的recursion
        // 从起点找edgeList，分别继续递归直到找不到edge（很直观的dfs）
        // 这时可能还有没用的票，这种不满足要求（太通用了也不行）

        // 递归过程需要记住dfs的track，就很麻烦
        // 不需要记录所有track最后排序，只需要在每个track终点与当前result比较

        // 但是还是超时了。。。

        while (!s.empty()) {
            string next = s.top();
            if (hash[next].empty()) {
                ans.push_back(next);
                s.pop();
            } else {
                s.push(*hash[next].begin());
                hash[next].erase(hash[next].begin());
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
    /*
    // [["AXA","EZE"],["EZE","AUA"],["ADL","JFK"],["ADL","TIA"],["AUA","AXA"],["EZE","TIA"],["EZE","TIA"],["AXA","EZE"],["EZE","ADL"],["ANU","EZE"],["TIA","EZE"],["JFK","ADL"],["AUA","JFK"],["JFK","EZE"],["EZE","ANU"],["ADL","AUA"],["ANU","AXA"],["AXA","ADL"],["AUA","JFK"],["EZE","ADL"],["ANU","TIA"],["AUA","JFK"],["TIA","JFK"],["EZE","AUA"],["AXA","EZE"],["AUA","ANU"],["ADL","AXA"],["EZE","ADL"],["AUA","ANU"],["AXA","EZE"],["TIA","AUA"],["AXA","EZE"],["AUA","SYD"],["ADL","JFK"],["EZE","AUA"],["ADL","ANU"],["AUA","TIA"],["ADL","EZE"],["TIA","JFK"],["AXA","ANU"],["JFK","AXA"],["JFK","ADL"],["ADL","EZE"],["AXA","TIA"],["JFK","AUA"],["ADL","EZE"],["JFK","ADL"],["ADL","AXA"],["TIA","AUA"],["AXA","JFK"],["ADL","AUA"],["TIA","JFK"],["JFK","ADL"],["JFK","ADL"],["ANU","AXA"],["TIA","AXA"],["EZE","JFK"],["EZE","AXA"],["ADL","TIA"],["JFK","AUA"],["TIA","EZE"],["EZE","ADL"],["JFK","ANU"],["TIA","AUA"],["EZE","ADL"],["ADL","JFK"],["ANU","AXA"],["AUA","AXA"],["ANU","EZE"],["ADL","AXA"],["ANU","AXA"],["TIA","ADL"],["JFK","ADL"],["JFK","TIA"],["AUA","ADL"],["AUA","TIA"],["TIA","JFK"],["EZE","JFK"],["AUA","ADL"],["ADL","AUA"],["EZE","ANU"],["ADL","ANU"],["AUA","AXA"],["AXA","TIA"],["AXA","TIA"],["ADL","AXA"],["EZE","AXA"],["AXA","JFK"],["JFK","AUA"],["ANU","ADL"],["AXA","TIA"],["ANU","AUA"],["JFK","EZE"],["AXA","ADL"],["TIA","EZE"],["JFK","AXA"],["AXA","ADL"],["EZE","AUA"],["AXA","ANU"],["ADL","EZE"],["AUA","EZE"]]

    // [["EZE","TIA"],["EZE","AXA"],["AUA","EZE"],["EZE","JFK"],["JFK","ANU"],["JFK","ANU"],["AXA","TIA"],["JFK","AUA"],["TIA","JFK"],["ANU","EZE"],["ANU","EZE"],["TIA","AUA"]]

    // vector<vector<string>> candiadteResult;
    vector<string> result;

    // [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        int ticketNum = tickets.size();
        vector<int> ticketFlag(ticketNum, 0);
        vector<string> track;
        track.emplace_back("JFK");
        recurse("JFK", tickets, ticketFlag, track);
        return result;
    }

    void recurse(string start, vector<vector<string>>& tickets, vector<int>& ticketFlag, vector<string>& track){
        auto sortFunc = [](vector<string>& trackLeft, vector<string>& trackRight)-> bool{
            int length = trackLeft.size();
            for (int i=0;i<length;i++){
                auto a = strcmp(trackLeft[i].c_str(), trackRight[i].c_str());
                if (a<0){
                    return true;
                } else if (a>0){
                    return false;
                }
            }
            return true;
        };

        vector<int> ticketsLeft = getTicketsDepart(start, tickets, ticketFlag);
        if (ticketsLeft.size() == 0){
            // candidate
            int usedTicketNum = accumulate(ticketFlag.begin(), ticketFlag.end(), 0);
            if (usedTicketNum == ticketFlag.size()){
                if (!sortFunc(result, track) or result.empty()){
                    result = track;
                }
            }
            return;
        } else{
            for (auto & ticketIndex : ticketsLeft){
                ;
                vector<int> newTicketFlag = ticketFlag;
                newTicketFlag[ticketIndex] = 1;
                string newStart = tickets[ticketIndex][1];
                vector<string> newTrack = track;
                newTrack.emplace_back(newStart);
                recurse(newStart, tickets, newTicketFlag, newTrack);
            }
        }
    }

    vector<int> getTicketsDepart(string start, vector<vector<string>>& tickets, vector<int>& ticketFlag){
        vector<int> res;
        for (int i=0;i<tickets.size();i++){
            if (tickets[i][0] == start and ticketFlag[i] == 0){
                res.push_back(i);
            }
        }
        return res;
    }
    */
};
// @lc code=end

int main(){
    vector<vector<string>> myTest{{"JFK","MUC"}, {"LHR","SFO"}, {"MUC","LHR"}};
    Solution mySolution;
    auto res = mySolution.findItinerary(myTest);
    for (auto& item : res){
        printf("%s ", item.c_str());
    }
    return 0;
}